class Solution:
    def restoreArray(self, adjacentPairs: list) -> list:
        adj = {}
        for pair in adjacentPairs:
            u, v = pair[0], pair[1]
            if u not in adj:
                adj[u] = set()
            if v not in adj:
                adj[v] = set()
            adj[u].add(v)
            adj[v].add(u)
        root = None
        for k, v in adj.items():
            if len(v) == 1:
                root = k
                break
        queue = [root]
        ans = []
        while queue:
            node = queue.pop(0)
            ans.append(node)
            for child in adj[node]:
                adj[child].remove(node)
                queue.append(child)

        return ans
